# LeetCode 114、二叉树展开为链表
# 一、题目描述
给你二叉树的根结点 root ，请你将它展开为一个单链表：
1、展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。
2、展开后的单链表应该与二叉树先序遍历顺序相同。
# 二、题目解析
# 三、参考代码
# 1、Java 代码
// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 二叉树展开为链表（ LeetCode 114 ）: https://leetcode-cn.com/problems/flatten-binary-tree-to-linked-list/
class Solution {
public void flatten(TreeNode root) {
backtrack(root);
}
// 传入二叉树的节点，把它转换为链表的形式，返回二叉树的尾节点
private TreeNode backtrack(TreeNode node){
// 1、如果 node 为空，返回 null
if(node == null) return null;
// 2、如果 node 为叶子节点，返回 node
if(node.left == null && node.right == null) return node;
// 下面开始设置几个指针
// 3、left 为当前节点 node 的左子树
TreeNode left = node.left;
// 4、right 为当前节点 node 的右子树
TreeNode right = node.right;
// 5、leftTail 指向当前节点左子树 left 转换为链表之后的尾节点，一开始默认为 null
TreeNode leftTail = null;
// 6、rightTail 指向当前节点右子树 right 转换为链表之后的尾节点，一开始默认为 null
TreeNode rightTail = null;
// 7、tail 指向以当前节点 node 为根节点转换为链表之后的尾节点，一开始默认为 null
TreeNode tail = null;
// 8、先将 node 的左子树指针置空
// 将 node 的左子树转换为链表之后，node 的右指针指向那个链表
node.left = null;
// 9、如果当前节点存在左子树的时候，那么把左子树转换为链表的形式
if(left != null){
// 通过 backtrack 函数递归的把当前节点的左子树转换为链表
// backtrack 函数指向完之后，left 已经是链表
// 根据第 5 点的代码，leftTail 指向左子树最后一个节点
leftTail = backtrack(left);
// 此时，node 的左子树 left 已经是链表的形式
// 那么将当前节点 node 的 right 指针指向 left，完成了当前节点和左子树链表的拼接
node.right = left;
// 根据第 7 ，tail 指向左子树最后一个节点
tail = leftTail;
}
// 10、如果当前节点存在右子树的时候，那么把左子树转换为链表的形式
if(right != null){
// 通过 backtrack 函数递归的把当前节点的右子树转换为链表
// backtrack 函数指向完之后，right 已经是链表
// 根据第 6 点的代码，rightTail 指向右子树最后一个节点
rightTail = backtrack(right);
// 此时，node 的右子树 right 已经是链表的形式
// 如果当前节点 node 不存在左子树，那么 node.left = null
// 由于 node 的右指针就是 right，所以不需要执行其它操作
// 但如果存在左子树，就需要把 left 链表和 right 链表串联起来
// 也就是把 left 链表的尾节点和 right 的头节点拼接起来
if(left != null){
// 将 leftTail 和 right 转换成的链表链接起来
leftTail.right = right;
}
// 如果存在右子树，那么根据第 7 点的代码，tail 指向右子树最后一个节点
tail = rightTail;
}
// 返回链表的尾节点位置继续去拼接其它的递归链表
return tail;
}
}
# **2、**C++ 代码
// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 二叉树展开为链表（ LeetCode 114 ）: https://leetcode-cn.com/problems/flatten-binary-tree-to-linked-list/
class Solution {
public:
void flatten(TreeNode* root) {
backtrack(root);
}
// 传入二叉树的节点，把它转换为链表的形式，返回二叉树的尾节点
TreeNode* backtrack(TreeNode* node){
// 1、如果 node 为空，返回 NULL
if(node == NULL) return NULL;
// 2、如果 node 为叶子节点，返回 node
if(node->left == NULL && node->right == NULL) return node;
// 下面开始设置几个指针
// 3、left 为当前节点 node 的左子树
TreeNode* left = node->left;
// 4、right 为当前节点 node 的右子树
TreeNode* right = node->right;
// 5、leftTail 指向当前节点左子树 left 转换为链表之后的尾节点，一开始默认为 NULL
TreeNode* leftTail = NULL;
// 6、rightTail 指向当前节点右子树 right 转换为链表之后的尾节点，一开始默认为 NULL
TreeNode* rightTail = NULL;
// 7、tail 指向以当前节点 node 为根节点转换为链表之后的尾节点，一开始默认为 NULL
TreeNode* tail = NULL;
// 8、先将 node 的左子树指针置空
// 将 node 的左子树转换为链表之后，node 的右指针指向那个链表
node->left = NULL;
// 9、如果当前节点存在左子树的时候，那么把左子树转换为链表的形式
if(left != NULL){
// 通过 backtrack 函数递归的把当前节点的左子树转换为链表
// backtrack 函数指向完之后，left 已经是链表
// 根据第 5 点的代码，leftTail 指向左子树最后一个节点
leftTail = backtrack(left);
// 此时，node 的左子树 left 已经是链表的形式
// 那么将当前节点 node 的 right 指针指向 left，完成了当前节点和左子树链表的拼接
node->right = left;
// 根据第 7 ，tail 指向左子树最后一个节点
tail = leftTail;
}
// 10、如果当前节点存在右子树的时候，那么把左子树转换为链表的形式
if(right != NULL){
// 通过 backtrack 函数递归的把当前节点的右子树转换为链表
// backtrack 函数指向完之后，right 已经是链表
// 根据第 6 点的代码，rightTail 指向右子树最后一个节点
rightTail = backtrack(right);
// 此时，node 的右子树 right 已经是链表的形式
// 如果当前节点 node 不存在左子树，那么 node->left = NULL
// 由于 node 的右指针就是 right，所以不需要执行其它操作
// 但如果存在左子树，就需要把 left 链表和 right 链表串联起来
// 也就是把 left 链表的尾节点和 right 的头节点拼接起来
if(left != NULL){
// 将 leftTail 和 right 转换成的链表链接起来
leftTail->right = right;
}
// 如果存在右子树，那么根据第 7 点的代码，tail 指向右子树最后一个节点
tail = rightTail;
}
// 返回链表的尾节点位置继续去拼接其它的递归链表
return tail;
}
};
# 3、Python 代码
# 登录 AlgoMooc 官网获取更多算法图解
# https://www.algomooc.com
# 作者：程序员吴师兄
# 代码有看不懂的地方一定要私聊咨询吴师兄呀
# 二叉树展开为链表（ LeetCode 114 ）: https://leetcode-cn.com/problems/flatten-binary-tree-to-linked-list/
class Solution:
def flatten(self, root: TreeNode) -> None:
self.backtrack(root)
# 传入二叉树的节点，把它转换为链表的形式，返回二叉树的尾节点
def backtrack(self, node: TreeNode) -> TreeNode :
# 1、如果 node 为空，返回 None
if not node :
return None
# 2、如果 node 为叶子节点，返回 node
if not node.left and not node.right :
return node
# 下面开始设置几个指针
# 3、left 为当前节点 node 的左子树
left = node.left
# 4、right 为当前节点 node 的右子树
right = node.right
# 5、leftTail 指向当前节点左子树 left 转换为链表之后的尾节点，一开始默认为 None
leftTail = None
# 6、rightTail 指向当前节点右子树 right 转换为链表之后的尾节点，一开始默认为 None
rightTail = None
# 7、tail 指向以当前节点 node 为根节点转换为链表之后的尾节点，一开始默认为 None
tail = None
# 8、先将 node 的左子树指针置空
# 将 node 的左子树转换为链表之后，node 的右指针指向那个链表
node.left = None
# 9、如果当前节点存在左子树的时候，那么把左子树转换为链表的形式
if left :
# 通过 backtrack 函数递归的把当前节点的左子树转换为链表
# backtrack 函数指向完之后，left 已经是链表
# 根据第 5 点的代码，leftTail 指向左子树最后一个节点
leftTail = self.backtrack(left)
# 此时，node 的左子树 left 已经是链表的形式
# 那么将当前节点 node 的 right 指针指向 left，完成了当前节点和左子树链表的拼接
node.right = left
# 根据第 7 ，tail 指向左子树最后一个节点
tail = leftTail
# 10、如果当前节点存在右子树的时候，那么把左子树转换为链表的形式
if right :
# 通过 backtrack 函数递归的把当前节点的右子树转换为链表
# backtrack 函数指向完之后，right 已经是链表
# 根据第 6 点的代码，rightTail 指向右子树最后一个节点
rightTail = self.backtrack(right)
# 此时，node 的右子树 right 已经是链表的形式
# 如果当前节点 node 不存在左子树，那么 node.left = None
# 由于 node 的右指针就是 right，所以不需要执行其它操作
# 但如果存在左子树，就需要把 left 链表和 right 链表串联起来
# 也就是把 left 链表的尾节点和 right 的头节点拼接起来
if left :
# 将 leftTail 和 right 转换成的链表链接起来
leftTail.right = right
# 如果存在右子树，那么根据第 7 点的代码，tail 指向右子树最后一个节点
tail = rightTail
# 返回链表的尾节点位置继续去拼接其它的递归链表
return tail